/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package grafox.Algorithms;

import grafox.Domain.GrafoX;
import grafox.Domain.VerticeX;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.LinkedList;

/**
 * Esta classe implementa o algoritmo de Busca por largura em um Grafo
 *
 * @author admindev
 */
public class BFS {

    private Hashtable<VerticeX, Long> distancia;
    private Hashtable<VerticeX,Long> tDescoberta;
    private long tempo;

    public Long getDistancia(VerticeX vertice) {
        return distancia.get(vertice);
    }

    public VerticeX getAntecessor(VerticeX vertice) {
        return antecessor.get(vertice);
    }

    /**
     *
     * @return Retorna a lista de antecessores
     */
    public Hashtable<VerticeX, VerticeX> getAntecessores() {
        return antecessor;
    }

    
    
    
    private Hashtable<VerticeX, VerticeX> antecessor;
    private Hashtable<VerticeX, String> cor;

    public BFS() {
        distancia = new Hashtable<>();
        antecessor = new Hashtable<>();
        tempo=0;
        tDescoberta=new Hashtable<>();


    }

    private String getCor(VerticeX vertice) {

        if (this.cor == null) {
            this.cor = new Hashtable<>();
        }

        return this.cor.get(vertice);

    }

    private void setCor(VerticeX vertice, String cor) {
        if (this.cor == null) {
            this.cor = new Hashtable<>();
        }

        this.cor.put(vertice, cor);
    }

    public static BFS realizarBFS(GrafoX grafo, VerticeX origem) {

        BFS bfs = new BFS();
        bfs.antecessor.clear();
        bfs.distancia.clear();


        for (VerticeX v : grafo.getVertices()) {
            bfs.setCor(v, "branco");
            bfs.distancia.put(v, Long.MAX_VALUE);

        }

        bfs.visitaBFS(origem);

        for (VerticeX v : grafo.getVertices()) {
            if ("branco".equals(bfs.getCor(v))) {
                bfs.visitaBFS(v);
            }
        }

        return bfs;

    }

    private void visitaBFS(VerticeX origem) {
      
        setCor(origem, "cinza");
        distancia.put(origem, new Long(0));
        tDescoberta.put(origem, ++tempo);
        

        LinkedList<VerticeX> fila = new LinkedList<>();
        fila.add(origem);

        while (fila.size() != 0) {
            VerticeX u = fila.pop();
            for (VerticeX v : u.getAdjacentes()) {
                if ("branco".equals(getCor(v))) {
                    v.visit();
                    setCor(v, "cinza");
                    tDescoberta.put(origem, ++tempo);
                    this.distancia.put(v, this.distancia.get(u) + 1);
                    antecessor.put(v, u);
                    fila.addLast(v);
                    v.terminate();
                }
            }
        }
        setCor(origem, "preto");


    }
}
